DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2013.116

Mutual Dimension

Authors: Adam Case and Jack H. Lutz

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract

We define the lower and upper mutual dimensions mdim(x:y) and Mdim(x:y) between any two points x and y in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by x and y. We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the data processing inequality for mutual dimension, says that, if f : R^m -> R^n is computable and Lipschitz, then the inequalities mdim(f(x):y) <= mdim(x:y) and Mdim(f(x):y) <= Mdim(x:y) hold for all x \in R^m and y \in R^t. We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.

Cite as

Adam Case and Jack H. Lutz. Mutual Dimension. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 116-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{case_et_al:LIPIcs.STACS.2013.116,
  author =	{Case, Adam and Lutz, Jack H.},
  title =	{{Mutual Dimension}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{116--126},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.116},
  URN =		{urn:nbn:de:0030-drops-39270},
  doi =		{10.4230/LIPIcs.STACS.2013.116},
  annote =	{Keywords: computable analysis, data processing inequality, effective fractal dimensions, Kolmogorov complexity, mutual information}
}

Search Results

Documents authored by Case, Adam

Mutual Dimension

Abstract

Cite as

Thanks for your feedback!

Could not send message